package Offer40;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * @author 23737
 * @time 2021.9.18
 * 最小的k个数：
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 */
public class Test {
    public static void main(String[] args) {
        int[] ints = new int[]{0,1,6,3,2,4,8};
        int[] leastNumbers = new Solution().getLeastNumbers(ints, 3);
        for (int i = 0; i < leastNumbers.length; i++) {
            System.out.println(leastNumbers[i]);
        }
    }
}

/*虽然过了，但是这道题也太简单了，而且我个人感觉面试官也不是在考我这种做法*/
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ints = new int[k];
        for (int i = 0; i < k; i++) {
            ints[i] = arr[i];
        }
        return ints;
    }

    /**
     * 使用栈来写
     * @param arr 数组
     * @param k 目标数目
     * @return 数组
     */
    public int[] getLeastNumbers2(int[] arr, int k) {
        Stack<Integer> stack = new Stack<>();
        int[] a = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            stack.push(arr[i]);
        }
        for (int i = arr.length; i > k; i--) {
            stack.pop();
        }
        for (int i = 0; i < k; i++) {
            a[i] = stack.pop();
        }
        return a;
    }
}


/*基于队列的实现,官方题解*/
class SolutionTwo {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}



